// Copyright (c) 2008-2010, Arne Claus
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the 
// following conditions are met:
//
// - Redistributions of source code must retain the above copyright notice, this list of conditions and the following 
//   disclaimer.
// - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following 
//   disclaimer in the documentation and/or other materials provided with the distribution.
// - Neither the name Arne Claus nor the names of any contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 
// USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef __INCLUDED_CBL_INTRUSIVE_LIST_H__
#define __INCLUDED_CBL_INTRUSIVE_LIST_H__

#include "CBL_Defines.h"

CB_NAMESPACE_START

// -------------------------------------------------------------------------------------
//	CIntrusiveList
//	A linked list style container that does not use wrapper container but the classes
//	itself to create a linked list. This way no extra allocations are necessary when
//	adding something to this kind of list.
//	List objects have to derive from CIntrusiveListItem.
//	An object can only be added to one TListId List at a time. To allow an object
//	to be linked to different lists at the same time increment the TListId for each
//	new list.
// -------------------------------------------------------------------------------------

template <typename TItemClass, uint32 TListId=0>
class CIntrusiveList
{
public:
	
	// -------------------------------------------------------------------------------------
	//	CItem
	//	Defines a baseclass for classes that need to be stored inside an intrusive List.
	// -------------------------------------------------------------------------------------
	
	class CItem
	{
	public:
		
		CItem() : m_pIntrusiveListParent(NULL), m_pIntrusiveListNext(NULL), m_pIntrusiveListPrev(NULL) {}
		virtual ~CItem() { if (m_pIntrusiveListParent) m_pIntrusiveListParent->Remove(static_cast<TItemClass&>(*this)); }
        
    private:
    
    	friend class CIntrusiveList;
		
		CIntrusiveList* m_pIntrusiveListParent;
		CItem*			m_pIntrusiveListPrev;
		CItem*			m_pIntrusiveListNext;
	};
	
public:
	
	CIntrusiveList();
	~CIntrusiveList();
	
	void PushBack(CItem& _rItem);
	void PushFront(CItem& _rItem);
	void Insert(CItem& _rItem, CItem& _rNewNext);
	
	void Remove(CItem& _rItem);
	CItem* PopFront();
	CItem* PopBack();
	void Clear();

public:
	
	bool IsEmpty();
	uint32 Size();
	
public:
	
	// -------------------------------------------------------------------------------------
	//	CIterator
	//	Wrapper for CItem to support iterator functionality (increment, decrement, etc.)
	// -------------------------------------------------------------------------------------
	
	class CIterator
	{
	public:
		
		CIterator(CItem* _pItem) : m_pCurrent(_pItem) {}
		
		CIterator operator ++ (int)					{ CItem* pLast = m_pCurrent; ++(*this); return CIterator(pLast); }
		void operator ++ ()							{ m_pCurrent = m_pCurrent->m_pIntrusiveListNext; }
		
		CIterator operator -- (int)					{ CItem* pLast = m_pCurrent; --(*this); return CIterator(pLast); }
		void operator -- ()							{ m_pCurrent = m_pCurrent->m_pIntrusiveListPrev; }
		
		CIterator& operator += (int _Count);
		CIterator operator + (int _Count);
		
		TItemClass& operator * ()					{ return *static_cast<TItemClass*>(m_pCurrent); }
		TItemClass* operator -> ()					{ return static_cast<TItemClass*>(m_pCurrent); }
		
		bool IsValid()								{ return m_pCurrent != NULL; }
		
		bool operator == (const CIterator& _rRhs)	{ return m_pCurrent == _rRhs.m_pCurrent; }
		bool operator != (const CIterator& _rRhs)	{ return m_pCurrent != _rRhs.m_pCurrent; }
		
	private:
		
		CItem* m_pCurrent;
	};
	
public:
	
	CIterator Begin();
	CIterator End();
	CIterator RBegin();	
	
private:
	
	CItem* m_pFirst;
	CItem* m_pLast;
	uint32 m_Size;
};

// -------------------------------------------------------------------------------------
//	Implementation
// -------------------------------------------------------------------------------------

#include "CBL_IntrusiveList.hpp"

CB_NAMESPACE_END

#endif